Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Exploration

摘要

In this paper, we consider the challenge of maximizing an unknown function ffor which evaluations are noisy and are acquired with high cost. An iterativeprocedure uses the previous measures to actively select the next estimation off which is predicted to be the most useful. We focus on the case where thefunction can be evaluated in parallel with batches of fixed size and analyzethe benefit compared to the purely sequential procedure in terms of cumulativeregret. We introduce the Gaussian Process Upper Confidence Bound and PureExploration algorithm (GP-UCB-PE) which combines the UCB strategy and PureExploration in the same batch of evaluations along the parallel iterations. Weprove theoretical upper bounds on the regret with batches of size K for thisprocedure which show the improvement of the order of sqrt{K} for fixediteration cost over purely sequential versions. Moreover, the multiplicativeconstants involved have the property of being dimension-free. We also confirmempirically the efficiency of GP-UCB-PE on real and synthetic problems comparedto state-of-the-art competitors.